#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : MonotoneIncreasingDigits.py
# @Time    : 2020/12/15 11:29
# @Description:


class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        """
        Given a non-negative integer N, find the largest number that is less than or equal to N with monotone
        increasing digits.

        (Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y
        satisfy x <= y.)

        Example 1:
            Input: N = 10
            Output: 9
        Example 2:
            Input: N = 1234
            Output: 1234
        Example 3:
            Input: N = 332
            Output: 299
        Note: N is an integer in the range [0, 10^9].

        :param N:
        :return:
        """
        nums = list(str(N))
        length = len(nums)
        begin = 0
        is_result = True
        max_num = float('-inf')
        for i in range(1, length):
            num = int(nums[i])
            pre_num = int(nums[i - 1])
            if pre_num > max_num:
                begin = i - 1
                max_num = pre_num
            if pre_num > num:
                is_result = False
                break
        if is_result:
            return N

        nums[begin] = str(int(nums[begin]) - 1)
        for i in range(begin + 1, length):
            nums[i] = '9'

        return int(''.join(nums))


if __name__ == '__main__':
    # N = 332
    # N = 10
    N = 1234
    S = Solution()
    print(S.monotoneIncreasingDigits(N))
    print('done')
